An Incremental Algorithm for the Maximum Flow Problem

An incremental algorithm may yield an enormous computational time saving to solve a network flow problem. It updates the solution to an instance of a problem for a unit change in the input. In this paper we have proposed an efficient incremental implementation of maximum flow problem after inserting an edge in the network G. The algorithm has the time complexity of O((n)² m), where n is the number of affected vertices and m is the number of edges in the network. We have also discussed the incremental algorithm for deletion of an edge in the network G.     

Flow Polynomials and Their Asymptotic Limits for Lattice Strip Graphs

We present exact calculations of flow polynomials F(G,q) for lattice strips of various fixed widths L _y 4 and arbitrarily great lengths L _x , with several different boundary conditions. Square, honeycomb, and triangular lattice strips are considered. We introduce the notion of flows per face fl in the infinite-length limit. We study the zeros of F(G,q) in the complex q plane and determine exactly the asymptotic accumulation sets of these zeros in the infinite-length limit for the various families of strips. The function fl is nonanalytic on this locus. The loci are found to be noncompact for many strip graphs with periodic (or twisted periodic) longitudinal boundary conditions, and compact for strips with free longitudinal boundary conditions. We also find the interesting feature that, aside from the trivial case L _y =1, the maximal point, q _cf , where crosses the real axis, is universal on cyclic and Möbius strips of the square lattice for all widths for which we have calculated it and is equal to the asymptotic value q _cf =3 for the infinite square lattice.     

Instabilities of micellar systems under homogeneous and non-homogeneous flow conditions

The rheological behavior of a cetylpyridinium chloride 100 mmol l^–1/sodium salicylate 60 mmol l^–1 aqueous solution was studied in this work under homogeneous (cone and plate) and non-homogeneous flow conditions (vane-bob and capillary rheometers), respectively. Instabilities consistent with non-monotonic flow curves were observed in all cases and the solution exhibited similar behavior under the different flow conditions. Hysteresis and the sigmoidal flow curve suggested as characteristic of systems that show constitutive instabilities were observed when running cycles of increasing and decreasing stress or shear rate, respectively. This information, together with a detailed determination of steady states at shear stresses close to the onset of the instabilities, allowed one to show unequivocally that "top and bottom jumping" are the mechanisms to trigger the instabilities in this micellar system. It is shown in addition that there is not a true plateau region in between the "top and bottom jumping". Finally, the flow behavior beyond the upturn seemed to be unstable and was found accompanied by an apparent violation of the no-slip boundary condition.     

Numerical analysis of buoyant flow in a hemispherical enclosure at high Rayleigh numbers

A numerical analysis is presented for buoyancy driven flow of a Newtonian fluid contained in a two dimensional (R, ) hemispherical enclosure for high Rayleigh (Ra) numbers. It is assumed that the flow is driven by the uniformly distributed internal heat sources within the enclosure. All walls of the cavity are maintained at a constant temperature. Finite volume based SIMPLER algorithm has been used for the present analysis. Discretised governing equations, in primitive variables, are solved by a combination of Three Diagonal Matrix Algorithm (TDMA) and Point Successive Overrelaxation (PSOR) method. A benchmark solution prepared for a Ra number range of 10⁷ to 10¹² and Prandtl (Pr) number 7.0, shows an excellent agreement with the experimental results obtained from the open literature.     

Sand Erosion in Axial Flow Conditions

A mathematical model of sand erosion in axial flow conditions is presented. The basic mass balance equations and sand erosion constitutive equation were given in Vardoulakis et al. (1996). As opposed to reference Vardoulakis et al. (1996), we consider here the extreme case where convection is null and hydrodynamic dispersion dominates. In addition, Brinkman's extension of Darcy's law is adopted to account for a smooth transition between channel flow and Darcian flow. The set of governing PDE's is presented in dimensionless form and is solved numerically. In concordance with the basic constitutive equation for erosion kinetics, the analysis shows that erosion progresses in time as a front of high transport concentration. This result is justified by the highly non-linear character of the erosion source term which dominates in the diffusion-like governing equation.     

Stability of a Pivoting Strategy for Parallel Gaussian Elimination

Gaussian elimination with partial pivoting achieved by adding the pivot row to the kth row at step k, was introduced by Onaga and Takechi in 1986 as means for reducing communications in parallel implementations. In this paper it is shown that the growth factor of this partial pivoting algorithm is bounded above by _n <#60; 3 ^n–1, as compared to 2 ^n–1 for the standard partial pivoting. This bound _n, close to 3 ^n–2, is attainable for class of near-singular matrices. Moreover, for the same matrices the growth factor is small under partial pivoting.This revised version was published online in October 2005 with corrections to the Cover Date.     

Dispersive flow of disks through a two-dimensional Galton board

We report here an experimental and numerical study of the flow properties of disks driven by gravity through a hexagonal lattice of obstacles, i.e. a Galton board. During the fall, particles experience dissipative collisions that scatter them in random directions. A driven-diffusion regime can be achieved under certain conditions. A characteristic length of the motion and its dependence on geometrical parameters of the system is analyzed in the steady regime. The influence of collective effects on the dispersion process is investigated by comparison between single- and many-particle flows. The characterization of the dynamics and the diffusive properties of the flow in a system like a Galton board can be expanded to other granular systems, particularly static solid particle mixers and will give some insight in understanding granular mixing.     

Monodisperse dry granular flows on inclined planes: Role of roughness

Recent studies have pointed out the importance of the basal friction on the dynamics of granular flows. We present experimental results on the influence of the roughness of the inclined plane on the dynamics of a monodisperse dry granular flow. We found experimentally that there exists a maximum of the friction for a given relative roughness. This maximum is shown to be independent of the slope angle. This behavior is observed for four planes with different bump sizes (given by the size of the beads glued on the plane) from 200 m to 2 mm. The relative roughness corresponding to the maximum of the friction can be predicted with a geometrical model of stability of one single bead on the plane. The main parameters are the size of the bumps and the size of the flowing beads. In order to obtain a higher precision, the model also takes into account the spacing between the bumps of the rough plane. Experimental results and model are in good agreement for all the planes we studied. Other parameters, like the sphericity of the beads, or irregularities in the thickness of the layer of glued particles, are shown to be of influence on the friction.     

Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices

A result of Balas and Yu (1989) states that the number of maximal independent sets of a graph G is at most ^p+1, where is the number of pairs of vertices in G at distance 2, and p is the cardinality of a maximum induced matching in G. In this paper, we give an analogue of this result for hypergraphs and, more generally, for subsets of vectors in the product of n lattices =₁××_n, where the notion of an induced matching in G is replaced by a certain binary tree each internal node of which is mapped into . We show that our bounds may be nearly sharp for arbitrarily large hypergraphs and lattices. As an application, we prove that the number of maximal infeasible vectors x=₁××_n for a system of polymatroid inequalities does not exceed max{Q,^logt/c(2Q,)}, where is the number of minimal feasible vectors for the system, , , and c(,) is the unique positive root of the equation 2^c(^c/log–1)=1. This bound is nearly sharp for the Boolean case ={0,1}ⁿ, and it allows for the efficient generation of all minimal feasible sets to a given system of polymatroid inequalities with quasi-polynomially bounded right-hand sides . This research was supported by the National Science Foundation (Grant IIS-0118635), and by the Office of Naval Research (Grant N00014-92-J-1375). The second and third authors are also grateful for the partial support by DIMACS, the National Science Foundation's Center for Discrete Mathematics and Theoretical Computer Science.Mathematics Subject Classification (2000):20E28, 20G40, 20C20     

Dynamic Global Constraints in Backtracking Based Environments

Global constraints provide strong filtering algorithms to reduce the search space when solving large combinatorial problems. In this paper we propose to make the global constraints dynamic, i.e., to allow extending the set of constrained variables during search. We describe a generic dynamisation technique for an arbitrary monotonic global constraint and we compare it with the semantic-based dynamisation for the alldifferent constraint. At the end we sketch a dynamisation technique for non-monotonic global constraints. A comparison with existing methods to model dynamic problems is given as well.